package org.algorithm.express;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Floyd {
    int v; // 顶点的个数
    int[][] path; // 记录各个顶点之间的最短路径
    int[][] graph;
    int[][] origin;
    static int INF = 65535; // 设置一个最大值

    List<String> pathList = new ArrayList<>();

    public Floyd(Graph graph) {
        this.v = graph.vCount;
        this.path = new int[v][v];
        this.graph = graph.graph;
        this.origin = this.graph.clone();
        for (int i = 0; i < this.graph.length; i++) {
            this.origin[i] = this.graph[i].clone();
        }
    }


    public int getMinPath(int[] packages) {
        // 先用floyd算法求得每个顶点到其他顶点的最短路径
        floydWarshall(graph);
        return minPath(packages);
    }

    public int getMinTime(int[] packages) {
        floydWarshall(graph);
        return minTime(packages);
    }

    private int minTime(int[] packages) {
        boolean[] visited = new boolean[packages.length];
        int start = 0; // 0 就是快递站
        int sum = 0;
        for (int i = 0; i < packages.length; i++) {

            //找到从当前起点出发路径最小的顶点
            int minIndex = -1;
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < packages.length; j++) {
                if (!visited[j] && this.graph[start][packages[j]] < min) {
                    min = this.graph[start][packages[j]];
                    minIndex = j;
                }
            }


            //更新访问
            visited[minIndex] = true;
            int next = packages[minIndex];
            int cost = (int) (((min / 10.0) * 60) + 10);
            System.out.printf("当前时间%3d min,当前位置: %2d 小区,选中第%2d个包裹,目的地: %2d 小区,距离为%d,预计耗时: %3d min | 路径:%s\n", sum, start, minIndex, next, min, cost, printPath(start, next));
            //更新起点
            start = next;
            //更新路径总和
            sum += cost;
        }

        return sum;
    }

    public int minPath(int[] packages) {

        boolean[] visited = new boolean[packages.length];
        int start = 0; // 0 就是快递站
        int sum = 0;
        for (int i = 0; i < packages.length; i++) {

            //找到从当前起点出发路径最小的顶点
            int minIndex = -1;
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < packages.length; j++) {
                if (!visited[j] && this.graph[start][packages[j]] < min) {
                    min = this.graph[start][packages[j]];
                    minIndex = j;
                }
            }


            //更新访问
            visited[minIndex] = true;
            int next = packages[minIndex];
            System.out.printf("当前位置: %d 小区,选中第%d个包裹,目的地: %d 小区,距离为%d,|路径:%s\n", start, minIndex, next, min, printPath(start, next));
            //更新起点
            start = next;
            //更新路径总和
            sum += min;
        }

        return sum;
    }

    public String printPath(int start, int end) {
        List<String> list = new ArrayList<>();
        getPath(start, end, list);
        return String.join("-", list);
    }

    public void getPath(int start, int end, List<String> list) {
        //起始顶点能否直达目标顶点
        if (this.origin[start][end] != Floyd.INF) {
            list.add(String.valueOf(start));
            list.add(String.valueOf(end));
            return;
        }

        list.add(String.valueOf(start));
        //起始顶点能否直达中间顶点
        if (this.origin[start][this.path[start][end]] != Floyd.INF) { //可以直达的话将中间顶点作为起始顶点进行递归
            getPath(this.path[start][end], end, list);
        } else { //不能直达中间顶点的话就找起始顶点与中间顶点的中间顶点
            getPath(this.path[start][this.path[start][end]], end, list);
        }
    }


    private void floydWarshall(int[][] graph) {
        int i, j, k;
        // 遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
        for (k = 0; k < v; k++) {
            for (i = 0; i < v; i++) {
                for (j = 0; j < v; j++) {
                    // 如果新的路径比之前记录的更短，则更新 graph 数组
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                        // 记录中间顶点
                        path[i][j] = k;
                    }
                }
            }
        }
    }
}